#include<string>
#include<vector>
using namespace std;

class WordDictionary {
private:
    struct Node {
        bool isEnd;
        vector<Node*> childs;
        Node():isEnd(false),childs(26) {

        }

    };

    Node* tree;

    bool search(Node* node, const string& word, int index) {
        if (node == NULL) return false;
        while (index < word.size() && word[index] != '.') {
            if (node->childs[word[index] - 'a'] == NULL)
                return false;
            node = node->childs[word[index] - 'a'];
            ++index;
        }
        if (index >= word.size())
            return node->isEnd;
        for (int i = 0; i < 26; ++i) {
            if (node->childs[i] != NULL && search(node->childs[i], word, index + 1))
                return true;
        }
        return false;

    }

public:
    /** Initialize your data structure here. */
    WordDictionary():tree(new Node()) {

    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        Node* node = tree;
        for (int i = 0; i < word.size(); ++i) {
            if (node->childs[word[i] - 'a'] == NULL)
                node->childs[word[i] - 'a'] = new Node();
            node = node->childs[word[i] - 'a'];
        }
        node->isEnd = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return search(tree, word, 0);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */